package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0313_01 {
    /**
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     * 同一个单元格内的字母不允许被重复使用。
     *
     * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
     * 输出：true
     *
     * 输入：board = [["a","b"],["c","d"]], word = "abcd"
     * 输出：false
     *
     * 提示：
     *
     * m == board.length
     * n = board[i].length
     * 1 <= m, n <= 6
     * 1 <= word.length <= 15
     * board 和 word 仅由大小写英文字母组成
     *
     * 思路分析：典型的矩阵搜索问题，可使用 深度优先搜索（dfs） + 剪枝 来解决
     * 深度优先搜锁：可以理解为暴力法遍历矩阵中所有字符串的可能性。DFS通过递归，先朝
     * 一个方向搜到底，再回溯到上个节点，沿另一个方向搜索，以此类推
     * 剪枝：在搜索中， 遇到 这条路不可能和目标字符串匹配成功 情况（例如：此举证元素和目标字符不同，此元素已被访问）
     * 则应该立即返回，称之为可行性剪枝
     *
     * DFS解析：
     * 递归参数：当前元素在矩阵 board 中行列的索引分别为 i和j，当前目标字符在 word 中的索引为k
     * 终止条件：
     * 1.返回false （1）行或者列索引越界 （2）当前 矩阵元素 和目标字符不匹配 （3）当前 矩阵元素 已经被访问过 （3）可以合并至（2）
     * 2.返回true： k=len（word）-1 ，即字符串word已全部匹配
     * 递推工作：
     * 1.标记当前矩阵元素：如何标记呢？ 将board[i][j] 修改为空字符‘’ ，代表此元素已访问过，
     * 放置之后搜索时重复访问
     * 2.搜索下一个单元格：朝 上、下、左、右四个方向开启下层递归，使用 或者 连接（代表只要找到一条可行的路径就直接返回，不再做
     * 后续的DFS），并记录结果到 res
     * 3. 还原当前矩阵：将board[i][j] 元素桓远之初始值，即word[k]
     *
     * 返回值：返回布尔值 res ，代表是否搜索到目标字符串
     *
     * 为什么要使用空字符（python：‘’,java/c++ ：‘\0’）做标记是为了放置标记字符与矩阵原有字符重复，当存在重复是
     * 此算法会将举证原有字符认作标记字符，从而出现错误
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        // 遍历图
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 开始递推工作
                // 如果找到了，就返回true，否则就继续赵
                if (dfs(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 深度优先搜索，先朝一个方向搜到底，如果没找到，再朝其他方向搜索
     * @param board 图 矩阵
     * @param word 目标字符串
     * @param i 行索引
     * @param j 列索引
     * @param k 目标字符的当前索引 k = len（word）- 1
     * @return
     */
    private boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 判断传入参数的可行性 i与图行数row比较，j与图列数col比较
        // k 是传入字符串当前索引，一开始是 0，如果当前字符串索引和图当前索引对应的值不相等，表示第一个数就
        // 所以继续找第一个相等的数。题目说第一个数位置不固定，即路径起点部固定（不一定是左上角的第一个数）

        // 如果board[i][j] == word[k] 则表明找到了对应的数，就继续执行（标记找过，继续dfs 下上右左）
        if (i >= board.length || i < 0 ||
        j >= board[0].length || j < 0 ||
        board[i][j] != word[k]){
            return false;
        }
        // 表示找完了，每个字符都找到了
        // 一开始k = 0 ，而word.length 肯定不是0,所以没找到，就执行dfs继续查找
        if (k == word.length - 1){
            return true;
        }
        // 访问过的标记空字符串，" " 是空格 '\0' 是空字符串，不一样的
        // 比如当前为A 没有标记找过，而且 A 是 word中对应元素，则此时应该找A的下一个元素，假设是 B ,
        // 在 dfs（B）的时候还是-> 要索索 B 左边的元素（假设A在B左边），所以就是 ABA（凭空多出了一个A，
        // 导致A用了2次，不可以），如果标记为空字符串->就不会出现这样的问题，因为他们的值不相等 AB != ABA
        board[i][j] = '\0';

        // 递推工作
        // 顺序是 下 上 右 左 ；上面找到了对应索引的值 所以 k + 1
        boolean res = dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) ||
                dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1);

        // 还原找过的元素，因为之后可能还会访问到（不同的路径）
        board[i][j] = word[k];

        // 返回结果，如果false ，则 if (dfs(board,words,i,j,0)){
        //                    return true;
        //                } 不会执行，就会继续找
        return res;
    }



    @Test
    public void m1() {

        char[][]  board =
                {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};

        String word = "ABCCED";
        boolean exist = this.exist(board, word);
        System.out.println("exist\t" + exist);

    }

    @Test
    public void m2() {
    }

}
